package com.example.system.class36;

/**
 * @Date 2022/9/10
 * @Author Jonathan
 * @Description AVL树
 */
public class Code01_AVLTreeMap {// 1:38

    /**
     * 这个k是可以比较的
     */
    public static class AVLNode<K extends Comparable<K>, V> {
        public K k;
        public V v;
        public AVLNode<K, V> l;
        public AVLNode<K, V> r;
        public int h;

        public AVLNode(K k, V v) {
            this.k = k;
            this.v = v;
            h = 1;
        }
    }


    public static class AVLTreeMap<K extends Comparable<K>, V> {
        private AVLNode<K, V> root;
        private int size;

        public AVLTreeMap() {
            this.root = null;
            this.size = 0;
        }

        /**
         * 右旋
         */
        private AVLNode<K, V> rightRotate(AVLNode<K, V> cur) {
            final AVLNode<K, V> left = cur.l;
            cur.l = left.r;
            left.r = cur;
            cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1;
            left.h = Math.max((left.l != null ? left.l.h : 0), left.r.h) + 1;
            return left;
        }
    }
}
